package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: Cengxubianli
 * @Auther: csy
 * @Date: 2021/3/14 01:00
 * @Description:
 */
public class Cengxubianli {
    private static final List<List<Integer>> TRAVERSAL_LIST = new ArrayList<>();

    public static class  TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        TreeNode treeNode5=new TreeNode(5);
        TreeNode treeNode7=new TreeNode(7);
        TreeNode treeNode8=new TreeNode(8);
        treeNode.left=treeNode2;
        treeNode.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        treeNode3.right=treeNode7;
        treeNode4.left=treeNode8;
        dfs(treeNode,0);
        levelOrderBottom(treeNode);
        System.out.println(TRAVERSAL_LIST);
    }

    /**
     * leetcdoe 102: 二叉树的层序遍历, 使用 dfs * @param root * @return
     */
    private static void dfs(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        if (TRAVERSAL_LIST.size() < level + 1) {
            TRAVERSAL_LIST.add(new ArrayList<Integer>());
        }
        List<Integer> levelList = TRAVERSAL_LIST.get(level);
        levelList.add(root.val);
        // 遍历左结点
        dfs(root.left, level + 1);
        // 遍历右结点
        dfs(root.right, level + 1);
    }
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        helper(root,0,res);
        return res;
    }

    // 一个前序遍历
    public static void helper(TreeNode root, int n, List<List<Integer>> res){
        if(root==null) {
            return;
        }
        // 取得同一层的链表 如果没有则 添加一个
        if(res.size()<=n) {
            res.add(0,new ArrayList<Integer>());
        }
        res.get(res.size()-n-1).add(root.val);
        helper(root.left,n+1,res);
        helper(root.right,n+1,res);
    }
}